from math import sqrt
import itertools, random

def prime():
    """Prime number generator using sieve of erastothenes."""
    yield 2
    D = {}
    q = 3
    while True:
        p = D.pop(q, 0)
        if p:
            x = q + p
            while x in D: x += p
            D[x] = p
        else:
            yield q
            D[q*q] = 2*q
        q += 2
            
def erastothenes(n):
    """Returns an ordered list containing all primes smaller than or equal to n."""
    nroot = int(sqrt(n))
    sieve = range(n+1)
    sieve[1] = 0

    for i in xrange(2, nroot+1):
        if sieve[i] != 0:
            m = n/i - i
            sieve[i*i:n+1:i] = [0] * (m+1)

    return filter(None, sieve)

def factor(n):
    """Returns an ordered list containing the prime factors of n."""
    primeGen = prime()
    result = []
    
    while n > 1:
        p = primeGen.next()
        
        while n % p == 0:
            result.append(p)
            n /= p

    return result

def nrDistinctFactors(n):
    primeGen = prime()
    result = 0
    
    while n > 1:
        p = primeGen.next()
        
        if n % p == 0:
            result += 1
            n /= p
        
        while n % p == 0:
            n /= p

    return result
    
def totient_gen(limit):
    """ Generates totient(n) for n in [1, limit] using a sieve method. """
    sieve = range(0, limit + 1)
    
    yield 1     # totient(1) == 1
    
    for i in xrange(2, limit + 1):
        if i == sieve[i]:
            for j in xrange(i, limit + 1, i):
                sieve[j] = sieve[j] * (i - 1) // i
                
        yield sieve[i]


class PrimeChecker:
    def __init__(self, limit):
        self.limit = limit
        self.primes = frozenset(erastothenes(limit))
        
    def is_prime(self, nr):
        if nr > self.limit:
            raise ValueError, "nr to be checked > limit"
        
        return nr in self.primes
